/***********************************************************************
 *                   Solver Pancake Problem 
 *					------------------------------------
 ***********************************************************************/


#include <windows.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#include "defsSolver.h"
#include "Parameters.h"
#include "TimeObject.h"
#include "ResultObject.h"
#include "HeuristicObject.h"
#include "Pancake.h"
#include "astar.h"
#include "Operators.h"

//////////////////////////////////////////////////////////////////////////////////////

Parameters *parm;
GameObject *gameObj;
ResultObject resObj;
HeuristicObject heuristicObj;
//////////////////////////////////////////////////////////////////////////////////////

int thresh;                                        /* search cutoff threshold */
int accLook;
int *firstState;
int ***ChildrenStates; //for each level - in order not to generate same child twice
I64 generatedInLevel;
I64 totalGeneratedForDistribute;
int *childStateForDiversity;



I64 HeuristicsValuesTable[40];
I64 DiverRandomTable[40];
I64 DiverMaxTable[40];
I64 totalExpanded;
char fMainLogName[100];
I64 totalEvaluated;


//////////////////////////////////////////////////////////////////////////////////////
UCHAR GetSpreadValuesOfChildren(int HuristicNumber,int *in_state);  
void FreeTopSpinMemory();      
void InitOperArray();                                  
void AllocateMemory();                                  
bool IDASTAR(int *firstState);
bool AStarSearch(int *firstState);
void PrintArray(int *arr);           
void PrintTiles(int *m_tiles);                        
bool search(int state[SIZE], int oldMove, int oldMoveDual, int g,int &delta,int prevDualHuristic);
bool ShouldSkipToDual(int hReg, int hDual, int g);
int DrillDown(int stateDual[],int curValue, int prevDualHuristic,int g,int oldMove,int childState[], int &lMove);

void Find_Diversity(int nProblems = -1,int iUseOnlyOperator=-1);
void Find_Diversity_TWO_DIM();
/////////////////////////////////////////////////////////////////////////////////////
int OperArray[SIZE];

Operators m_OperObj;
			

// Function name	: PrintArray
// Description	    : Prints the array
// Return type		: void 
// Argument         : int *arr
void PrintArray(int *arr)
{
	printf("Array[] = ");
//	fprintf(fLog,"Array[] =");
	for (int i=0;i<SIZE;i++)
	{
		printf("%d ",arr[i]);
//		fprintf(fLog,"%d ",arr[i]);
	}
	printf("\n");
//	fprintf(fLog,"\n");
}

// Function name	: PrintTiles
// Description	    : 
// Return type		: void 
// Argument         : int *m_tiles
void PrintTiles(int *m_tiles)
{
	printf("Tiles[] ");
	for (int i=0;i<PATTERNSIZE;i++)
		printf("%d ",m_tiles[i]);
	printf("\n");
}





// Function name	: AllocateMemory
// Description	    : Allocate Memory needed
// Return type		: void 
void AllocateMemory()
{
	parm = new Parameters;
	gameObj = new GameObject;

	childStateForDiversity = new int[SIZE];
	firstState = new int[SIZE];

	ChildrenStates = new int**[(SIZE<<2)];
	for (int i=0;i<(SIZE<<2);i++)
	{
		ChildrenStates[i] = new int*[SIZE];
		for (int j=0;j<SIZE;j++)
			ChildrenStates[i][j] = new int[SIZE];
	}
	for (int i=0;i<40;i++)
	{
		HeuristicsValuesTable[i]=0;
		DiverRandomTable[i] = 0;
		DiverMaxTable[i] = 0;
	}
	totalEvaluated = 0;

}

// Function name	: FreeTopSpinMemory
// Description	    : Free Memory
// Return type		: void 
void FreeTopSpinMemory()
{

	
	delete[] firstState;
	for (int i=0;i<(SIZE<<2);i++)
	{
		for (int j=0;j<SIZE;j++)
			delete[] ChildrenStates[i][j];
		delete[] ChildrenStates[i];
	}
	delete[] ChildrenStates;
	delete[] childStateForDiversity;
	delete gameObj;
	delete parm;
}




/*
 0 - name for search
 1 - name for overall distribution
  */
char *GetNameForLog(int i)
{
	char* fLogName = new char[100];
	char *tmp = new char[10];
	if (i==1)
		strcpy(fLogName,"OverAllDis_S");
	else
		strcpy(fLogName,"S");
	itoa(SIZE,tmp,10);
	strcat(fLogName,tmp);
	strcat(fLogName,"P");
	itoa(PATTERNSIZE,tmp,10);
	strcat(fLogName,tmp);

/*	if (i!=1)
	{
		if (USE_ASTAR)
			strcat(fLogName,"Astar");
		else
			strcat(fLogName,"IDA");
	}*/
	strcat(fLogName,"H");
	itoa(heuristicObj.currentHeuristicNumber,tmp,10);
	strcat(fLogName,tmp);

	if (i!=1)
	{
		if (heuristicObj.currentUseCutOff)
			strcat(fLogName,"_BPMX");

		if (Should_Avoid_LOOPS)
			strcat(fLogName,"_AL");

		if (SKIP_TO_DUAL)
		{
			strcat(fLogName,"_Jump");
			if (Allways_Skip)
				strcat(fLogName,"_Allways");
		}
		if (UseOperator == BigToSmall )
		{
			strcat(fLogName,"_BTS");
		}
		if (UseOperator == BigToSmall17H2)
		{
			strcat(fLogName,"_BTSH2");
		}
		if (UseOperator == OneLevelIRE)
		{
			strcat(fLogName,"_BTSH1");
		}

	}

	strcpy(fMainLogName,fLogName);
	strcat(fMainLogName,".gbl\0");
	strcat(fLogName,".txt\0");
	return fLogName;
}




////////////////////////////////////////////////////////////////
//                            MAIN                            //
////////////////////////////////////////////////////////////////

void main(int argc, char *argv[])
{
	int state[SIZE];
	TimeObject objTime;
	bool bFoundSolution;
	char *LogFileName=NULL;
 
	AllocateMemory(); 
	InitOperArray();
	parm->initialize(argc,argv);
	printf ("init db table \n");
	resObj.SetParameters(parm);

	if (GenerateProblemsFile == 0)
	{
		heuristicObj.Initialize(parm, gameObj);
		heuristicObj.Reset();
	}
	if (Should_Get_OverAll_Distribution)
	{
		heuristicObj.AnalysePDB();
		exit (0);
	}
	if (FIND_DIVERSITY)
	{
		heuristicObj.currentHeuristicNumber = parm->m_heuristicLowerBound;
		if (DIVERSITY_T == IRE_TWO_DIM)
			Find_Diversity_TWO_DIM();

		if (DIVERSITY_T == IRN)
		{
			Find_Diversity();
		}

		if (DIVERSITY_T == IRE)
		{
			for (int i=1;i<17;i++)
			{
				Find_Diversity(10,i);
			}
		}
		return;
	}

	
	for (heuristicObj.currentHeuristicNumber = parm->m_heuristicLowerBound ; heuristicObj.currentHeuristicNumber <= parm->m_heuristicHigherBound;heuristicObj.currentHeuristicNumber++)
		for (heuristicObj.currentUseCutOff = parm->m_UseCutOffLowerBound ; heuristicObj.currentUseCutOff <=parm->m_UseCutOffHigherBound ; heuristicObj.currentUseCutOff++)
		{
			if (heuristicObj.currentHeuristicNumber == 0 && heuristicObj.currentUseCutOff == 1)
				continue;
			LogFileName = GetNameForLog(0);
			resObj.SetOutputFileName(LogFileName);

			for (int problem = 1; problem < parm->m_iFirstProblem + parm->m_nProblemsToSolve; problem++)
			{
				srand(problem);
				parm->readNextProblem(state, ReadProblemsFromFile);
				if (GenerateProblemsFile)
				{
					FILE *filePtr;
					filePtr = fopen("problems.d","a+");
					fprintf(filePtr,"%d\t", problem);
					for (int k=0;k<SIZE;k++)
						fprintf(filePtr,"%d ", state[k]);
					fprintf(filePtr,"\n");
					fclose(filePtr);
					continue;
				}
				gameObj->PrintArray(state);
				if (problem <parm->m_iFirstProblem)
				{
					printf("%d\tSkiping Problem\n",problem);
					resObj.m_skipProblem++;
					continue;
				}

				if (PrintMainLog)
				{
					FILE *fMainLog;
					fMainLog = fopen(fMainLogName,"a+");
					fprintf(fMainLog,"%d\t", problem);
					for (int k=0;k<SIZE;k++)
						fprintf(fMainLog,"%d ", state[k]);
					fprintf(fMainLog,"\n");
					fclose(fMainLog);
				}

				resObj.resetCurrent();
				heuristicObj.Reset();
				

			
				objTime.Start();
				if (USE_IDA_STAR_SEARCH)
					bFoundSolution =  IDASTAR(state);
				else
					bFoundSolution = AStarSearch(state);

				
				resObj.SetSolveTime(objTime.Stop());
				resObj.PrintCurent();
				resObj.AddToGlobalResults();
			}
			resObj.PrintGlobalResults();
			if (LogFileName)
				delete[] LogFileName;
		}

		if (Should_Get_Run_Time_Heuristic_Distribution)
		{
			resObj.PrintHeuristicDistributionArray(HeuristicsValuesTable);
		}

	FreeTopSpinMemory();
}





//first time - search(s,-1,0,nback)
//sec..		 - search(s,move,g+1,nback)
bool search(int state[SIZE], int oldMove, int oldMoveDual, int g,int &delta, int prevDualHuristic)
{

	int childState[SIZE];
	int stateDual[SIZE];
	int newMove;
	int hReg =0, hDual = 0, hMax=0;
	bool bShouldJump = false;

	if (heuristicObj.currentHeuristicNumber != 1)
		hReg = heuristicObj.eval(state);

	if (heuristicObj.currentHeuristicNumber > 0)
	{	//if use dual
		gameObj->ConvarteStateToDual(state, stateDual);
		
			hDual = heuristicObj.eval(stateDual);

		if (MaximizeTimePreformances == 0 || oldMove > (SIZE - PATTERNSIZE))
		{
			hDual = heuristicObj.eval(stateDual);
		}
		else
			hDual = prevDualHuristic;

	}

	hMax = MAX(hReg, hDual);
	if (Should_Get_Run_Time_Heuristic_Distribution)
	{
		HeuristicsValuesTable[hMax] = HeuristicsValuesTable[hMax] + 1;
		totalEvaluated++;				
		if (Maximum_Number_Of_Nodes == totalEvaluated)
		{
			resObj.PrintHeuristicDistributionArray(HeuristicsValuesTable);
			FreeTopSpinMemory();
			exit(0);
		}
	}


	delta = hMax + g - thresh;
	if (delta > 0)
		return false;
	
	int sChild[SIZE];
	int lMove;
	if (heuristicObj.currentHeuristicNumber > 0 )//&& delta > -3)
	{	//if use dual
		int hTmp = DrillDown(state,hDual, prevDualHuristic,g,oldMove, sChild,lMove);
		hDual = MAX(hDual,hTmp);
		prevDualHuristic = hDual;
		hMax = MAX(hReg, hDual);

		delta = hMax + g - thresh;
		if (delta > 0)
			return false;
	}


	if (hMax==0 && gameObj->IsGoal(state))
	{
		if (PRINT_SOLUTION_PATH)
			PrintArray(state);
		return true;
	}

	bShouldJump = ShouldSkipToDual(hReg, hDual, g);

	if (bShouldJump)
	{
		int tmp = oldMove;
		oldMove = oldMoveDual; 
		oldMoveDual = tmp;
	}

	int accBF = 0;
	int k;
	for(k = 0; k < SIZE ; k++)
	{
//		newMove = OperArray[k];
		newMove = m_OperObj.GetAt(oldMove,k);
		if (Should_Avoid_LOOPS && newMove == oldMove || newMove ==0)
			continue;
		accBF++;
		
//		if (lMove != newMove)
		{
			if (bShouldJump)
				gameObj->MakeMove(stateDual,childState,newMove);
			else
				gameObj->MakeMove(state,childState,newMove);
			generatedInLevel++;
		}


//		if (lMove != newMove)
//		{
			if (search(childState , newMove, oldMoveDual, g+1 ,delta,prevDualHuristic))
				return true; 
//		}
//		else
//		{
//			if (search(sChild , newMove, oldMoveDual, g+1 ,delta,prevDualHuristic))
//				return true; 
//		}

		
		if (heuristicObj.currentUseCutOff)
		{
			delta = delta - 2; // - ((g(pop->child) + h(pop->child)) = 2) 
			if (delta > 0)
			{
				resObj.m_currentTotalCut++;
				resObj.m_currentTotalBranching = resObj.m_currentTotalBranching +accBF;
				resObj.m_currentTotalFullyExpended = resObj.m_currentTotalFullyExpended + 1;
				return false;
			}
		}
		else
			delta = 0;
	}
	resObj.m_currentTotalBranching = resObj.m_currentTotalBranching +accBF;
	resObj.m_currentTotalFullyExpended = resObj.m_currentTotalFullyExpended + 1;
	return false;
}
/*
//Befor adding OperArray
bool search(int state[SIZE], int oldMove, int oldMoveDual, int g,int &delta)
{
	int childState[SIZE];
	int stateDual[SIZE];
	int newMove;
	int hReg =0, hDual = 0, hMax=0;
	bool bShouldJump = false;

	if (heuristicObj.currentHeuristicNumber != 1)
		hReg = heuristicObj.eval(state);

	if (heuristicObj.currentHeuristicNumber > 0)
	{	//if use dual
		gameObj->ConvarteStateToDual(state, stateDual);
		hDual = heuristicObj.eval(stateDual);
	}

	hMax = MAX(hReg, hDual);
	if (Should_Get_Run_Time_Heuristic_Distribution)
	{
		HeuristicsValuesTable[hMax] = HeuristicsValuesTable[hMax] + 1;
		totalEvaluated++;				
		if (Maximum_Number_Of_Nodes == totalEvaluated)
		{
			resObj.PrintHeuristicDistributionArray(HeuristicsValuesTable);
			FreeTopSpinMemory();
			exit(0);
		}
	}


	delta = hMax + g - thresh;
	if (delta > 0)
		return false;
	
	if (hMax==0 && gameObj->IsGoal(state))
	{
		if (PRINT_SOLUTION_PATH)
			PrintArray(state);
		return true;
	}

	bShouldJump = ShouldSkipToDual(hReg, hDual, g);

	if (bShouldJump)
	{
		int tmp = oldMove;
		oldMove = oldMoveDual; 
		oldMoveDual = tmp;
	}

	if (OperateOperatorsFromBigToSmall == 0)
	{
		for(newMove = 1; newMove < SIZE; newMove++)
		{
			if (Should_Avoid_LOOPS && newMove == oldMove)
				continue;
			
			if (bShouldJump)
				gameObj->MakeMove(stateDual,childState,newMove);
			else
				gameObj->MakeMove(state,childState,newMove);

			generatedInLevel++;

			if (search(childState , newMove, oldMoveDual, g+1 ,delta))
				return true; 

			
			if (heuristicObj.currentUseCutOff)
			{
				delta = delta - 2; // - ((g(pop->child) + h(pop->child)) = 2) 
				if (delta > 0)
				{
					resObj.m_currentTotalCut++;
					return false;
				}
			}
			else
				delta = 0;
		}
	}
	else
	{
		for(newMove = SIZE - 1; newMove > 0; newMove--)
		{
			if (Should_Avoid_LOOPS && newMove == oldMove)
				continue;
			
			if (bShouldJump)
				gameObj->MakeMove(stateDual,childState,newMove);
			else
				gameObj->MakeMove(state,childState,newMove);

			generatedInLevel++;

			if (search(childState , newMove, oldMoveDual, g+1 ,delta))
				return true; 

			
			if (heuristicObj.currentUseCutOff)
			{
				delta = delta - 2; // - ((g(pop->child) + h(pop->child)) = 2) 
				if (delta > 0)
				{
					resObj.m_currentTotalCut++;
					return false;
				}
			}
			else
				delta = 0;
		}
	}

	return false;
}*/


// Function name	: MY_GAME::IDASTAR
// Description	    : 
// Return type		: bool 
// Argument         : string firstState
// Argument         : int huristicNumber
// Argument         : long &nEpxendNodes
// Argument         : int &depth

bool IDASTAR(int *firstState)
{
	accLook = 0;
	int stateDual[SIZE];
	int hReg = 0, hDual = 0, hMax = 0;
	bool boo;
	bool bShouldSkip = false;
	int prevDualHuristic = 0;


	if (heuristicObj.currentHeuristicNumber != 1)
		hReg = heuristicObj.eval(firstState);
	
	//if use dual
	if (heuristicObj.currentHeuristicNumber > 0)
	{
		gameObj->ConvarteStateToDual(firstState, stateDual);
		hDual = heuristicObj.eval(stateDual);
		prevDualHuristic = hDual;
	}
	hMax = MAX(hReg, hDual);
	if (Should_Get_Run_Time_Heuristic_Distribution)
	{
		HeuristicsValuesTable[hMax] = HeuristicsValuesTable[hMax] + 1;
		totalEvaluated++;				
		if (Maximum_Number_Of_Nodes == totalEvaluated)
		{
			resObj.PrintHeuristicDistributionArray(HeuristicsValuesTable);
			FreeTopSpinMemory();
			exit(0);
		}
	}
	

	resObj.currentGeneretedNodes++;
	thresh = hMax;
	if (hMax==0) //so can be goal
		if (gameObj->IsGoal(firstState))
			return true;

	int delta = 0;

	if (SKIP_TO_DUAL)
		bShouldSkip = ShouldSkipToDual(hReg, hDual, 0);

	do
	{
		delta = 0;
		generatedInLevel =0;
		if (bShouldSkip)
			boo = search(stateDual , -1 , -1, 0, delta,prevDualHuristic);
		else
			boo = search(firstState , -1 , -1, 0, delta,prevDualHuristic);

		resObj.currentGeneretedNodesTillLastIter = resObj.currentGeneretedNodes;
		resObj.currentGeneretedNodes += generatedInLevel;
		
		if (SHOULD_PRINT_THERASH)
		{
			printf("Trush = %u Generated In Level %I64d        Total Cut %I64d\n",thresh,generatedInLevel,resObj.m_currentTotalCut);
			if (PrintMainLog)
			{
				FILE *fMainLog;
				fMainLog = fopen(fMainLogName,"a+");
				fprintf(fMainLog,"Trush = %u\tGenerated %I64d (%I64d)\tCut %I64d\tJump %I64d\n",
					thresh,
					resObj.currentGeneretedNodes,
					generatedInLevel,
					resObj.m_currentTotalCut,
					resObj.m_currentJumps);
				fclose(fMainLog);
			}
		}
		if (boo)
		{
			resObj.currentDepth = thresh;
			return true;
		}
		thresh = MAX(thresh + delta, thresh + 1);
	}while (boo==false);
	return true;
}



bool ShouldSkipToDual(int hReg, int hDual, int g)
{
	if (SKIP_TO_DUAL == 0)
		return false;
	if (Allways_Skip == 1)
	{
		resObj.m_currentJumps++;
		return true;
	}

	if ((hDual - hReg)>0)
	{
		resObj.m_currentJumps++;
		return true;
	}

	return false;
}

void Find_Diversity(int nProblems, int iUseOnlyOperator)
{
	bool bModeDebug = false;
	nProblems = 1000000;


	int state[SIZE];
	int stateDual[SIZE];
	int child[SIZE];
	int childDual[SIZE];

	int diversityArr[100];
	int randomDiverArr[100];
	int maximumDiversityArr[100];
	int minimumDiversityArr[100];

	int MaxDiversity;
	int MinDiversity;
	
	int h, hChild, hDual, hReg, diver;

	heuristicObj.currentHeuristicNumber = HEURISTIC_LOWER_BOUND;
	

//	nProblems = 100;

	for (int j=0;j<100;j++)
	{
		minimumDiversityArr[j] = 0;
		randomDiverArr[j] = 0;
		diversityArr[j] = 0;
		maximumDiversityArr[j] = 0;
	}

	for (int i = 0; i < nProblems ; i++)
	{
		if (i %1000 == 0)
			printf("%d\r",i);
		srand(i);
		parm->readNextProblem(state, 0);
		hDual = 0; hReg = 0;
		if (heuristicObj.currentHeuristicNumber != 1)
			hReg = heuristicObj.eval(state);


		if (heuristicObj.currentHeuristicNumber > 0)
		{	//if use dual
			gameObj->ConvarteStateToDual(state, stateDual);
			hDual = heuristicObj.eval(stateDual);
			if (bModeDebug)
			{
				printf("State - ");
				PrintArray(state);
				printf("Dual  - ");
				PrintArray(stateDual);
			}

		}
		h = MAX(hReg, hDual);		

		MaxDiversity = 0;
		MinDiversity = 100;

		int irand;
		if (iUseOnlyOperator == -1)
			irand = (rand() % (SIZE - 1)) + 1;
		else
			irand = iUseOnlyOperator;

		
		for (int newMove=1; newMove < SIZE; newMove++)
		{
			if (iUseOnlyOperator > -1)
			{
				newMove = iUseOnlyOperator;
			}
			gameObj->MakeMove(state,child,newMove);

//			printf("\n");
//			PrintArray(state);
//			PrintArray(child);


			if (heuristicObj.currentHeuristicNumber != 1)
				hReg = heuristicObj.eval(child);

			if (heuristicObj.currentHeuristicNumber > 0)
			{	//if use dual
				gameObj->ConvarteStateToDual(child, childDual);
				hDual = heuristicObj.eval(childDual);
//				PrintArray(childDual);
			}
			hChild = MAX(hReg, hDual);
			diver = abs(hChild - h);
			if (newMove == irand)
			{
				randomDiverArr[diver] +=1;
			}
			MaxDiversity = max(MaxDiversity, diver);
			MinDiversity = min(MinDiversity, diver);
			diversityArr[diver] ++;
			if (iUseOnlyOperator > -1)
			{
				break;
			}
		}

		maximumDiversityArr[MaxDiversity]++;
		minimumDiversityArr[MinDiversity]++;

	}

/*	printf("\nDiversity Array\n");
	for (j=0;j<100;j++)
	{
		if (diversityArr[j] > 0)
		{
			printf("%d\t%d\n",j,diversityArr[j]);
		}
	}*/


	char* fLogName = new char[100];
	char *tmp = new char[10];
	if (iUseOnlyOperator>-1)
	{
		strcpy(fLogName,"Diversity_Operator_");
		itoa(iUseOnlyOperator,tmp,10);
		strcat(fLogName,tmp);
		strcat(fLogName,".txt");
	}
	else
		strcpy(fLogName,"Diversity.txt");


	FILE *fPtr = fopen(fLogName,"a+");
	if (iUseOnlyOperator == -1)
	{
		fprintf(fPtr,"\nMaximum Diversity Array\n");
		for (int j=0;j<100;j++)
		{
			if (maximumDiversityArr[j] > 0)
			{
				fprintf(fPtr,"%d\t%d\n",j,maximumDiversityArr[j]);
				printf("%d\t%d\n",j,maximumDiversityArr[j]);
			}
		}
	}
/*
	printf("\nMinimum Diversity Array\n");
	for (j=0;j<100;j++)
	{
		if (minimumDiversityArr[j] > 0)
		{
			printf("%d\t%d\n",j,minimumDiversityArr[j]);
		}
	}*/

	fprintf(fPtr,"\nRandom Diversity Array\n");
	for (int j=0;j<100;j++)
	{
		if (randomDiverArr[j] > 0)
		{
			fprintf(fPtr,"%d\t%d\n",j,randomDiverArr[j]);
			printf("%d\t%d\n",j,randomDiverArr[j]);
		}
	}
	fclose(fPtr);
	delete[] fLogName;
	delete[] tmp;
}


I64 hashFullState(int *state)
{
	I64 hashval;  /* accumulator for hash value */
	int i, j;              /* utility indices */
	int digit;             /* single digit in factorial base */
 
	hashval = 0;           /* initialize hash value to empty */
	for (int i = 0; i < SIZE; i++)   /* for each remaining position in permutation */
	{
		digit = state[i];         /* initially digit is value in permutation */
		for (int j = 0; j < i; j++)   /* for each previous element in permutation */
		if (state[j] < state[i]) digit--; /* previous position contains smaller value, decrement digit*/
		hashval = hashval * (SIZE - i) + digit;
	}   /* multiply digit by appropriate factor */
	return (hashval);
}


I64 hashFullState2(NodeState nodeRotated)
{
	I64 hashval;  /* accumulator for hash value */
	int i, j;              /* utility indices */
	int digit;             /* single digit in factorial base */
 
	hashval = 0;           /* initialize hash value to empty */
	for (int i = 0; i < SIZE; i++)   /* for each remaining position in permutation */
	{
		digit = nodeRotated.state[i];         /* initially digit is value in permutation */
		for (int j = 0; j < i; j++)   /* for each previous element in permutation */
		if (nodeRotated.state[j] < nodeRotated.state[i]) digit--; /* previous position contains smaller value, decrement digit*/
		hashval = hashval * (SIZE - i) + digit;
	}   /* multiply digit by appropriate factor */
	return (hashval);
}

bool goal(NodeState p) 
{
	//State should be rotated
	for (int i=0 ; i < SIZE; i++)
	{
		if (p.state[i]!=i)
			return false;
	}
	
	return true;
}

unsigned char hfunction(NodeState p) 
{
	unsigned char Hval;
	int mState[SIZE];
	for (int i=0; i<SIZE; i++)
		mState[i] = (int)(p.state[i]);
	Hval = (unsigned char)heuristicObj.eval(mState);
	return Hval;
}

I64 GetHashValueOfNodeDual(NodeState parent)
{
	int mState[SIZE];
	int stateDual[SIZE];
	for (int i=0; i<SIZE; i++)
		mState[i] = (int)(parent.state[i]);

	gameObj->ConvarteStateToDual(mState, stateDual);
	I64 retValue = hashFullState(&stateDual[0]);
	return retValue;
}

NodeState *makeChildren(NodeState parent,int &sizeArray) 
{
	resObj.m_currentExpended++;
	NodeState *ptr_Children;
	sizeArray = 0;
	unsigned char hDual = 0, hReg = 0, hMax; 

	ptr_Children = new NodeState[(SIZE-1)*2];

	int childState[SIZE];
	int mState[SIZE];
	int stateDual[SIZE];

	for (int i=0; i<SIZE; i++)
		mState[i] = (int)(parent.state[i]);

	int acc = 0;
	for (int newMove = 1; newMove < SIZE; newMove++)
	{
		if (WHEN_USING_ASTAR_USE_OPERATOR_PRUNING  && newMove == parent.m_LastMove)
			continue;
		acc++;

		gameObj->MakeMove(mState, childState, newMove);

		if (heuristicObj.currentHeuristicNumber != 1)
			hReg = heuristicObj.eval(childState);
		
		//if use dual
		if (heuristicObj.currentHeuristicNumber > 0)
		{
			gameObj->ConvarteStateToDual(childState, stateDual);
			hDual = heuristicObj.eval(stateDual);
		}
		hMax = MAX(hReg, hDual);
//		PrintArray(childState);	
		if (SOULD_PUSH_ALL_CHIILDREN == 0)
		{
			if (ShouldSkipToDual(hReg, hDual,0) == false)
			{
				ptr_Children[acc-1].Initialize(childState, 0 , hMax);
				ptr_Children[acc-1].m_LastMove = newMove;
				ptr_Children[acc-1].m_LastTmpMove = parent.m_LastTmpMove ;

			}
			else
			{
				resObj.m_currentJumps++;
				ptr_Children[acc-1].Initialize(stateDual, 0 , hMax);
				ptr_Children[acc-1].m_LastMove = parent.m_LastTmpMove;
				ptr_Children[acc-1].m_LastTmpMove = newMove;
			}
			sizeArray ++;
		}
		else
		{
			ptr_Children[(acc-1)*2].Initialize(childState, 0 , hMax);
			ptr_Children[(acc-1)*2].m_LastMove = newMove;
			ptr_Children[(acc-1)*2].m_LastTmpMove = parent.m_LastTmpMove ;

			ptr_Children[(acc-1)*2+1].Initialize(stateDual, 0 , hMax);
			ptr_Children[(acc-1)*2+1].m_LastMove = parent.m_LastTmpMove;
			ptr_Children[(acc-1)*2+1].m_LastTmpMove = newMove;

			sizeArray = sizeArray+2;
		}
	}

	return ptr_Children;
}


bool AStarSearch(int *firstState)
{
	Astar AstarObj;
	NodeState root;
	I64 hashVal;
	unsigned char Hval;

	hashVal = hashFullState(firstState);
	Hval = heuristicObj.eval(firstState);

	root.Initialize(firstState, 0, Hval);

	///////////////////////////////////////////////
	I64 m_thresh = 0;
	I64 m_generated = 0;
	I64 m_totalExpanded = 0;

	int UpdateFromListsCut = 1;
	int depth = AstarObj.AStarSearch( root, hfunction, goal, makeChildren, 
		hashFullState2 ,  heuristicObj.currentUseCutOff, resObj.currentGeneretedNodes, 
		totalExpanded, UpdateFromListsCut, GetHashValueOfNodeDual);
	resObj.currentDepth = depth;

	return true;
}


void InitOperArray()
{
	//0 - 17
	int i;
	if (UseOperator == SmallToBig || SIZE!=17)
	{
		for (int i=0;i<SIZE;i++)
			OperArray[i]=i;
		return;
	}
	if (UseOperator == BigToSmall)
	{
		for (int i=0;i<SIZE;i++)
			OperArray[i]=SIZE - 1 - i;
		return;
	}
	
	if (UseOperator == BigToSmall17H2)
	{//BigToSmall17H2 15,14,13,12,16,11 - 0
		for (int i=0;i<SIZE;i++)
			OperArray[i]=SIZE - 1 - i;
		OperArray[0] = 15;
		OperArray[1] = 14;
		OperArray[2] = 13;
		OperArray[3] = 12;
		OperArray[4] = 16;
		return;
	}

	if (UseOperator == OneLevelIRE)
	{//BigToSmall17H2 15,14,16,13 - 0
		for (int i=0;i<SIZE;i++)
			OperArray[i]=SIZE - 1 - i;
		OperArray[0] = 15;
		OperArray[1] = 14;
		OperArray[2] = 16;
		return;
	}
}

int DrillDown(int stateDual[],int curValue, int prevDualHuristic,int g,int oldMove, int childState[], int &newMove)
{
	if (UNIQUE_LOOK_AHEAD == NONE)
	{
			return -1;
	}

	int childStateDual[SIZE];
//	int newMove;
	int relevantMove = SIZE - PATTERNSIZE + 1 ;
	int hVal =0;
	double averageHueristicFunction = 9.2;
	bool bShouldEvaluate = false;
	int probToDig;
	int rRand =  rand()%100;
	newMove = rand()%(PATTERNSIZE -1) + relevantMove;
//	newMove = rand()%(SIZE-1) + 1;
	if (newMove == oldMove)
	{
		newMove = -1;
		return -1;
	}


	switch (UNIQUE_LOOK_AHEAD)
	{
		case NONE:
			bShouldEvaluate = false;
			break;
		case ALWAYS:
			bShouldEvaluate = true;
			break;
		case BPMX1:
			probToDig = (1 - (double)g/(double)SIZE)*30;
			probToDig = probToDig + (averageHueristicFunction - curValue) * 50;
			bShouldEvaluate = rRand < probToDig;
			break;
		case BPMX2:
			if (g > 5 || curValue >=9)
				bShouldEvaluate = false;
			else
			{
				probToDig = (1 - (double)g/(double)SIZE)*40;
				probToDig = probToDig + (averageHueristicFunction - curValue) * 50;
				bShouldEvaluate = rRand < probToDig;
			}
	}
	
	bool bDebug = false;
	if (bShouldEvaluate)
	{
		resObj.currentLookedStates++;

		gameObj->MakeMove(stateDual,childState,newMove);
		gameObj->ConvarteStateToDual(childState, childStateDual);
		hVal =  heuristicObj.eval(childStateDual) - 1;
		if (hVal > curValue && bDebug)
		{
			printf("%d\t%d\t%d\t%d\n",curValue,hVal,newMove,g);
			if (resObj.currentLookedStates > 1000)
				exit(0);
		}
		return hVal;
	}
	newMove = -1;
	return -1;
}


int GetStateH(int state[SIZE])
{
	int hReg = 0;
	int hDual = 0;
	int h;
	int SDual[SIZE];

	if (heuristicObj.currentHeuristicNumber != 1)
		hReg = heuristicObj.eval(state);


	if (heuristicObj.currentHeuristicNumber > 0)
	{	//if use dual
		gameObj->ConvarteStateToDual(state, SDual);
		hDual = heuristicObj.eval(SDual);
	}
	h = MAX(hReg, hDual);		
	return h;
}

void Find_Diversity_TWO_DIM()
{
	//according to grandfather
	int iOp1,iOp2,i,j,hG,hC,hdP,hdC,diff;
	FILE *fPtr;
	double diver;
	bool bModeDebug = false;
	int nProblems = 10000000;

	int G[SIZE];
	int GDual[SIZE];
	int P[SIZE];
	int C[SIZE];
	int CDual[SIZE];

	int IRE_DiverArray[50];

	fPtr = fopen("TwoDimDiver.txt","a+");
	fprintf(fPtr,"FirstSecond\t");
	for ( i =1;i<SIZE;i++)
	{
		fprintf(fPtr,"%d\t",(i+1));
	}


	//////////////////////////////////////
	for (iOp1 = 0; iOp1<SIZE;iOp1++)
	{

		fprintf(fPtr,"\n%d\t",(iOp1+1));
		for (iOp2 = 1; iOp2<SIZE;iOp2++)
		{
			printf("%d\t%d\n",(iOp1+1),(iOp2+1));
			for (i = 0; i< 50; i++)
				IRE_DiverArray[i]=0;

			for (int iProblem = 0; iProblem < nProblems; iProblem++)
			{
				//generate random state		    -   G
				//generate G child using iOp1   -	P
				//generate P child using iOp2   -   C
				srand(iProblem);
				parm->readNextProblem(G, 0);
				gameObj->MakeMove(G,P,iOp1);
				gameObj->MakeMove(P,C,iOp2);
				//compare hG to hC
				hG = 0; hC =0;
				hG = GetStateH(G);
				hC = GetStateH(C);
				diff = abs(hC - hG);
				IRE_DiverArray[diff]++;
			}
			//calc diversity
			diver = 0;
			for (i=0;i<50;i++)
				diver += i*IRE_DiverArray[i];
			diver = diver / nProblems;
			fprintf(fPtr,"%f\t",diver);
		}
	}
	fclose(fPtr);
}
